A common vector coding technique quantizes and encodes the residual signal after adaptive filtering according to one type of fixed codebook, e.g., algebraic codebook. The algebraic codebook is concerned about the pulse position of a target signal and considers the pulse amplitude as 1 by default. Therefore, it is only necessary to quantize the pulse symbol and pulse position. Surely, multiple pulses can be superimposed in one position to represent different amplitudes. When quantization and coding are performed according to the algebraic codebook, it is an important activity to determine the positions of all pulses of the optimal algebraic codebook corresponding to the target signal. Generally, a full search (i.e., traverse all possible position combinations) for the optimal pulse position is subject to complex computation. It is therefore necessary to find a sub-optimal search algorithm. It is a main goal of search algorithm research and development to minimize the number of searches and reduce the complexity of computation while guaranteeing the quality of a search result.
A Depth-First Tree Search Procedure is described below to explain a sub-optimal searching method adopted in algebraic codebook based pulse position search according to a prior art.
Suppose, for example, the length of a speech subframe is 64 bits. Depending on the bit rate of coding, the number of pulses to search for (hereunder referred to as search pulses) varies. Suppose, for example, the number is N. Without other restrictions, searching for N pulses at 64 positions requires overly-complex computations. Therefore, the method constrains the pulse positions of the algebraic codebook by dividing the 64 positions into M tracks. A typical track planning model is described in Table 1.
TABLE 1TrackPositionsT00, 4, 8, 12, 16, 20, 24, 28, 32 36, 40, 44, 48, 52, 56, 60T11, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61T22, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62T33, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63
In Table 1, T0-T3 are 4 tracks and positions specify the position numbers included by each track. The 64 positions are divided into 4 tracks and each track contains 16 positions. The pulse positions of the 4 tracks are interlaced with each other to guarantee the combinations of all pulse positions to the greatest extent.
The N search pulses are restrained to the M=4 tracks according to a certain distribution mode. The following description assumes N=4 and 1 pulse is located on each track. The search procedure in other occasions can be deduced from this description.
Suppose, for example, the search pulses on T0-T3 are respectively P0-P3, and each search process searches for two pulses on two adjacent tracks, for example, T0-T1, T1-T2, T2-T3, and T3-T0. The final optimal codebook is obtained by a 4-level search. As shown in FIG. 1, the procedure includes the following blocks:
Block 1: A level-1 search is performed on T0-T1 and T2-T3. First, the positions of P0 and P1 are searched for on T0-T1, where P0 is searched for in 4 of the 16 positions on T0. The 4 positions are determined by extreme values of known reference signals on the track; P1 is searched for in the 16 positions on T1. The optimal positions of P0 and P1 are determined among the 4 position combinations searched for according to a preset criterion. Then the positions of P2 and P3 are searched for on T2-T3, where P2 is searched for in 8 of the 16 positions on T2. The 8 positions are determined by extreme values of known reference signals on the track; P3 is searched for in the 16 positions on T3. Finally, the optimal positions of P2 and P3 are determined. The level-1 search is complete.
Block 2: A level-2 search is performed on T1-T2 and T3-T0. The search process is similar to the level-1 search.
Block 3: Similarly, a level-3 search is performed on T2-T3 and T0-T1, and a level-4 search is performed on T3-T0 and T1-T2.
Block 4: Finally, an optimal result among the four search results is selected as the optimal algebraic codebook.
The total number of searches is 4×(4×16+8×16)=768.
However, it has been found that, although the foregoing search algorithm obtains good speech quality under various bit rates, the number of searches is large and the computation is complex.